package com.tgy.树.线索二叉树;

/***
 * @ClassName: Node
 * @Description: 线索节点
 * @Auther: tanggy3
 * @Date: 12:52 2022/12/23
 * @version : V1.0
 */
public class Node {
    public int no;
    public String name;
    public Node leftNode;
    public Node rightNode;
    //说明
    //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    //2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
    public int leftType;
    public int rightType;
    boolean b = false;

    /**
     * 二叉树的遍历
     */
    //编写前序遍历的方法
    public void preOrder() {
        //根节点
        System.out.println(this);
        //左节点
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        //右节点
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }


    //中序遍历
    public void midOrder() {
        //左节点
        if (this.leftNode != null) {
            this.leftNode.midOrder();
        }
        //根节点
        System.out.println(this);
        //右节点
        if (this.rightNode != null) {
            this.rightNode.midOrder();
        }
    }


    //后序遍历
    public void postOrder() {
        //左节点
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        //右节点
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        //根节点
        System.out.println(this);
    }

    /**
     * 二叉树的查找
     */

    //快速查找
    public void quickFind(Node targetNode) {
        if (targetNode.no > this.no) {
            this.rightNode.quickFind(targetNode);
        } else if (targetNode.no < this.no) {
            this.leftNode.quickFind(targetNode);
        } else {
            System.out.println("找到根节点");
        }
    }

    //前序查找
    public Node preFind(int targetNode) {
        System.out.println("进入前序查找");
        //比较当前结点是不是
        if (this.no == targetNode) {
            return this;
        }
        //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2.如果左递归前序查找，找到结点，则返回
        Node resNode = null;
        if (this.leftNode != null) {
            resNode = this.leftNode.preFind(targetNode);
        }
        if (resNode != null) {//说明我们左子树找到
            return resNode;
        }
        //1.左递归前序查找，找到结点，则返回，否继续判断，
        //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.rightNode != null) {
            resNode = this.rightNode.preFind(targetNode);
        }
        return resNode;
    }

    //中序查找
    public Node midFind(int targetNode) {
        Node resNode = null;
        if (this.leftNode != null) {
            resNode = this.leftNode.midFind(targetNode);
        }
        if (resNode != null) {//说明我们左子树找到
            return resNode;
        }
        System.out.println("进入中序查找");
        if (targetNode == this.no) {
            return this;
        }
        if (this.rightNode != null) {
            resNode = this.rightNode.midFind(targetNode);
        }
        return resNode;
    }

    //后序查找
    public Node postFind(int targetNode) {
        Node resNode = null;
        if (this.leftNode != null) {
            resNode = this.leftNode.postFind(targetNode);
        }
        if (resNode != null) {//说明我们左子树找到
            return resNode;
        }
        if (this.rightNode != null) {
            resNode = this.rightNode.postFind(targetNode);
        }
        if (resNode != null) {//说明我们右子树找到
            return resNode;
        }
        System.out.println("进入后序查找");
        if (targetNode == this.no) {
            return this;
        }
        return resNode;
    }


    /**
     * 删除节点
     * 如果删除的节点是根节点就整个删除
     * 如果删除的节点是叶子节点，则删除该节点
     * 如果删除的节点是非叶子节点，则删除该子树.
     * 测试，删除掉 5号叶子节点 和 3号子树.
     */

    /**
     * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
     * 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
     * 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
     * 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
     * 5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
     */
    public boolean delNode(int targetNo) {

        //向左查找如果是就删除
        if (this.leftNode != null && this.leftNode.no == targetNo) {
            this.leftNode = null;
            b =  true;
            return b;
        }
        //向右查找，如果是就删除
        if (this.rightNode != null && this.rightNode.no == targetNo) {
            this.rightNode = null;
            b =  true;
            return b;
        }
        //非当前节点的第一子节点则递归删除
        if (this.leftNode != null && this.leftNode.no != targetNo) {
            b = this.leftNode.delNode(targetNo);
        }
        if (this.rightNode != null && this.rightNode.no != targetNo) {
            b = this.rightNode.delNode(targetNo);
        }
        return b;
    }


    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }


}
